package 图.岛屿问题;

import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/12 12:25
 */
public class leetcode695岛屿的最大面积 {

    /*
     AC
     沉岛思想，代码写起来会更简洁一些，
     直接用不到 map 数组
     https://leetcode.cn/problems/max-area-of-island/solutions/150127/biao-zhun-javadong-tai-gui-hua-jie-fa-100-by-mark-/?orderBy=hot


     这个题，也可以用 并查集的思想来写！
     */
    public int solution(int grid[][]) {
        int m = grid.length;
        int n = grid[0].length;
        int map[][] = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 1) {
                    ans = Math.max(ans, recursion(m, n, i, j, map, grid));
                }
            }
        }
        return ans;
    }

    public int recursion(int m, int n, int i, int j, int[][] map, int grid[][]) {
        if (i == m || j == n || i < 0 || j < 0) {
            return 0;
        }
        if (grid[i][j] == 0 || map[i][j] == 1) {
            return 0;
        }
        map[i][j] = 1;
        int ans = 1;
        ans += recursion(m, n, i + 1, j, map, grid);
        ans += recursion(m, n, i, j + 1, map, grid);
        ans += recursion(m, n, i - 1, j, map, grid);
        ans += recursion(m, n, i, j - 1, map, grid);
        return ans;
//        Thread t1 = new Thread();

    }


    // 这个题 非常 适合 用 并查集 来写

    public int solve(int matrix[][]) {

        UF uf = new UF(matrix); // 初始化并查集
        int col = matrix[0].length;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int cur = i * matrix[0].length + j;
                if (matrix[i][j] == 1) {
                    if (i - 1 >= 0 && matrix[i - 1][j] == 1) {
                        uf.union(cur, (i - 1) * col + j);
                    }
                    if (i + 1 < matrix.length && matrix[i + 1][j] == 1) {
                        uf.union(cur, (i + 1) * col + j);
                    }
                    if (j - 1 >= 0 && matrix[i][j - 1] == 1) {
                        uf.union(cur, (i) * col + j - 1);
                    }
                    if (j + 1 < matrix[0].length && matrix[i][j + 1] == 1) {
                        uf.union(cur, (i) * col + j + 1);
                    }
                }
            }
        }
        int ans = 0;
        // 可以 遍历 求最大的值, 也可以 直接 在 union 的时候 直接 更新 max , 但感觉都差不多
        for(int i = 0;i < uf.size.length;i++){
            ans = Math.max(ans,uf.size[i]);
        }

        return ans;
    }

    static class UF {

        int[] parent;
        int size[];
        int sets;

        public UF(int matrix[][]) {
            parent = new int[matrix.length * matrix[0].length];
            size = new int[matrix.length * matrix[0].length];
            int col = matrix[0].length;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 1) {
                        parent[i * col + j] = i * col + j; // 将坐标 映射成节点
                        size[i * col + j] = 1;
                        sets++;
                    }
                }
            }
        }

        public int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            return parent[x] = find(parent[x]);
        }


        public void union(int x, int y) {
            int xp = find(x), yp = find(y);
            if (xp != yp) {
                parent[xp] = yp;
                size[yp] += size[xp];
                sets--;
            }
        }
    }

}


